Qué (quién) es Вычислимая функция - definición

Вычислимые функции — это множество функций вида, ${\displaystyle f\colon N\to N,}$ которые могут быть реализованы на машине Тьюринга. Задачу вычисления функции ${\displaystyle f}$ называют алгоритмически разрешимой или алгоритмически неразрешимой, в зависимости от того, возможен ли алгоритм, вычисляющий эту функцию.

В качестве множества ${\displaystyle N}$ обычно рассматривается множество ${\displaystyle B^{*}}$ — множество слов в двоичном алфавите ${\displaystyle B=\{0,1\}}$, с оговоркой, что результатом вычисления может быть не только слово, но и специальное значение «неопределённость», соответствующее случаю, когда алгоритм «зависает». Таким образом, можно дать следующее определение ${\displaystyle N}$:

${\displaystyle N=B^{*}\cup \{\operatorname {undef} \},}$

где ${\displaystyle B=\{0,1\}}$, а ${\displaystyle \operatorname {undef} }$ — специальный элемент, означающий неопределённость.

Роль множества ${\displaystyle N}$ может играть множество натуральных чисел, к которому добавлен элемент ${\displaystyle \operatorname {undef} }$, и тогда вычислимые функции — это некоторое подмножество натуральнозначных функций натурального аргумента. Удобно считать, что в качестве ${\displaystyle N}$ могут выступать различные счётные множества — множество натуральных чисел, множество рациональных чисел, множество слов в каком-либо конечном алфавите и др. Важно, чтобы существовал некоторый формальный язык в конечном алфавите описания элементов множества ${\displaystyle N}$ и чтобы задача распознавания корректных описаний была вычислима. Например, для описания натуральных чисел удобно использовать двоичную систему счисления — язык описания натуральных чисел в алфавите ${\displaystyle B}$.

В данном определении вместо исполнителя машин Тьюринга можно взять один из Тьюринг-полных исполнителей. Грубо говоря, «эталонным исполнителем» может быть некоторый абстрактный компьютер, подобный используемым персональным компьютерам, но с потенциально бесконечной памятью и особенностями архитектуры, позволяющими использовать эту бесконечную память.

Важно отметить, что множество программ для этого исполнителя (например, множество машин Тьюринга при фиксированном алфавите входных и выходных данных) счётно. Поэтому множество вычислимых функций не более чем счётно, в то время как множество функций вида ${\displaystyle f\colon N\to N,}$ несчётно, если ${\displaystyle N}$ счётно. Значит, есть невычислимые функции, причём мощность их множества больше, чем мощность множества вычислимых функций. Примером невычислимой функции (алгоритмически неразрешимой проблемы) может быть функция определения остановки — функция, которая получает на вход описание некоторой машины Тьюринга и вход для неё, а возвращает 0 или 1 в зависимости от того, остановится данная машина на данном входе или нет. Ещё одним примером невычислимой функции является колмогоровская сложность.